#include<iostream>

using namespace std;

void changeTurn(char& turn);
void displayGameBoard(int xMoves, int oMoves);
void getMove(int& xMoves, int& oMoves, char turn);
bool playerMovedAtPosition(int moves, int position);
bool playerWon(int moves);
bool catWon(int xMoves, int oMoves);

void main()
{
	int xMoves = 0;
	int oMoves = 0;

	char turn = 'X';

	bool continueGame = true;


	while(continueGame)
	{
		displayGameBoard(xMoves, oMoves);
		getMove(xMoves, oMoves, turn);
			//get a move for current user

		if(playerWon(xMoves))
		{
			cout << "X wins!!!" << endl;
			continueGame = false;
		}
		else if(playerWon(oMoves))
		{
			cout << "O wins!!" << endl;
			continueGame = false;
		}
		else if(catWon(xMoves, oMoves))
		{
			cout << "CAT wins!!" << endl;
			continueGame = false;
		}
		//check if game is over
		changeTurn(turn);
	}


}	

bool playerWon(int moves)
{
	bool result = false;

	if((moves & 14) == 14 ||
		(moves & 112) == 112 ||
		(moves & 896) == 896 ||
		(moves & 146) == 146 ||
		(moves & 168) == 168 ||
		(moves & 292) == 292 ||
		(moves & 546) == 546 ||
		(moves & 584) == 584 )
	{
		result = true;
	}

	return result;
}

bool catWon(int xMoves, int oMoves)
{
	bool result = false;
	
	if(xMoves + oMoves == 1022)
	{
		result = true;
	}

	return result;
}


void changeTurn(char& turn)
{
	if(turn == 'X')
	{
		turn = 'O';
	}
	else
	{
		turn = 'X';
	}
}

bool playerMovedAtPosition(int moves, int position)
{
	int powerOf2AtPosition = (int)pow(2.0,position); 
	return ((moves &  powerOf2AtPosition)== powerOf2AtPosition);
}

void displayGameBoard(int xMoves, int oMoves)
{
	int position = 1;
	for(int i = 0; i < 3; i++)
	{
		for(int j = 0; j < 3;j++)
		{
			if(playerMovedAtPosition(xMoves,position))
			{
				cout << 'X';
			}
			else if(playerMovedAtPosition(oMoves,position))
			{
				cout << 'O';
			}
			else
			{
				cout << position;
			}

			if(j < 2)
			{
				cout << "|";
			}

			position++;
		}
		if(i < 2)
		{
			cout << endl << "-|-|-" << endl;
		}
	}
}

void getMove(int& xMoves, int& oMoves, char turn)
{
	int newMove;
	bool validMove = true;
	
	do
	{
		cout << turn << "'s Turn: ";
		cin >> newMove;

		if(newMove < 1 || 
			newMove > 9 ||
			playerMovedAtPosition(xMoves,newMove) ||
			playerMovedAtPosition(oMoves,newMove))
		{
			cout << "Invalid move. " << endl;
			validMove = false;
		}
		else
		{
			validMove = true;
		}
	}
	while(!validMove);

	if(turn == 'X')
	{
		xMoves += pow(2.0, newMove);
	}
	else
	{
		oMoves += pow(2.0, newMove);
	}
}